
// https://leetcode.cn/problems/reverse-pairs/
class Solution1
{
    int v[50000];

public:
    int reversePairs(vector<int> &nums)
    {
        return Sort(nums, 0, nums.size() - 1);
    }

    int Sort(vector<int> &nums, int left, int right)
    {
        if (left >= right)
            return 0;
        int mid = rand() % (right - left + 1) + left;
        int count = 0;
        count = Sort(nums, left, mid) + Sort(nums, mid + 1, right);
        int l = left, r = mid + 1, j = 0;
        while (l <= mid && r <= right)
        {
            if (nums[l] / 2.0 > nums[r])
            {
                count += right - r + 1;
                l++;
            }
            else
            {
                r++;
            }
        }
        for (l = left, r = mid + 1, j = 0; l <= mid && r <= right;)
        {
            if (nums[l] > nums[r])
                v[j++] = nums[l++];
            else
                v[j++] = nums[r++];
        }
        while (l <= mid)
            v[j++] = nums[l++];
        while (r <= right)
            v[j++] = nums[r++];
        for (int i = left; i <= right; i++)
        {
            nums[i] = v[i - left];
        }
        return count;
    }
};

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

//https://leetcode.cn/problems/add-two-numbers/
class Solution2
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        long long i = 1, num1 = 0, num2 = 0;
        ListNode *ll = new ListNode();
        ListNode *head = ll;
        ListNode *l = nullptr;
        while (l1 != nullptr || l2 != nullptr)
        {
            if (l1 != nullptr && l2 != nullptr)
            {
                num1 = l1->val + l2->val + num2;
                l1 = l1->next;
                l2 = l2->next;
            }
            else if (l1 == nullptr && l2 != nullptr)
            {
                num1 = l2->val + num2;
                l2 = l2->next;
            }
            else
            {
                num1 = l1->val + num2;
                l1 = l1->next;
            }
            if (num1 >= 10)
            {
                num2 = 1;
                num1 %= 10;
            }
            else
                num2 = 0;
            l = new ListNode();
            l->val = num1;
            ll->next = l;
            ll = l;
            if (l1 == nullptr && l2 == nullptr && num2 == 1)
            {
                l = new ListNode();
                l->val = num2;
                ll->next = l;
                ll = l;
            }
        }
        return head->next;
    }
};

//优化版
class Solution2_1 {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        long long i = 1, num1 = 0,num2 = 0;
        ListNode* ll = new ListNode();
        ListNode* head = ll;
        while(l1 != nullptr || l2 != nullptr || num1) 
        {
            if(l1)
            {
                num1 += l1->val;
                l1 = l1->next;
            }
            if(l2)
            {
                num1 += l2->val;
                l2 = l2->next;
            }
            ll->next = new ListNode(num1 % 10);
            ll = ll->next;
            num1 /= 10;
        }
        return head->next;
    }
};